struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

 //使用归并的思路
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 边界情况：空链表或只有一个节点，直接返回
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // 1. 拆分链表：用快慢指针找中点，分成左右两部分
        ListNode* mid = findMid(head);
        ListNode* rightHead = mid->next;
        mid->next = nullptr; // 断开左右链表，避免循环

        // 2. 递归排序左右两部分
        ListNode* left = sortList(head);
        ListNode* right = sortList(rightHead);

        // 3. 合并两个有序链表
        return mergeTwoSortedList(left, right);
    }

private:
    // 辅助函数1：快慢指针找链表中点（左半部分偏短）
    ListNode* findMid(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head->next; // 快指针先多走一步，确保拆分后左半部分偏短
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 辅助函数2：合并两个有序链表
    ListNode* mergeTwoSortedList(ListNode* l1, ListNode* l2) {
        ListNode dummy(0); // 虚拟头节点，简化连接逻辑
        ListNode* cur = &dummy;

        // 逐个比较两个链表节点，按序连接
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }

        // 连接剩余未遍历完的链表
        cur->next = (l1 != nullptr) ? l1 : l2;

        return dummy.next;
    }
};